package com.gaofeng.algo.java;

import java.util.*;

public class GreedyJava {

    public static void main(String[] args) {
        int[][] intervals = new int[][]{{1, 2}, {2, 4}, {1, 3}};
        int result = eraseOverlapping(intervals);
        System.out.println("result:" + result);
    }

    private static int findContentChildren(int[] children, int[] cookies) {
        Arrays.sort(children);
        Arrays.sort(cookies);

        int child = 0;
        int cookie = 0;
        while (child < children.length && cookie < cookies.length) {
            if (children[child] <= cookies[cookie]) {
                child++;
            }
            cookie++;
        }
        return child;
    }

    /**
     * 135.分发糖果
     * 题目描述
     * 一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一
     * 个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所
     * 有孩子至少要有一个糖果。求解最少需要多少个糖果。
     * 输入输出样例
     * 输入是一个数组，表示孩子的评分。输出是最少糖果的数量。
     * Input: [1,0,2]
     * Output: 5
     * 在这个样例中，最少的糖果分法是 [2,1,2]。
     *
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        int size = ratings.length;
        int[] candys = new int[size];
        Arrays.fill(candys, 1);
        for (int i = 1; i < size; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candys[i] = candys[i - 1] + 1;
            }
        }

        for (int i = size - 1; i > 0; i--) {
            if (ratings[i - 1] > ratings[i]) {
                candys[i - 1] = Math.max(candys[i] + 1, candys[i - 1]);
            }
        }
        int total = 0;
        for (int i = 0; i < size; i++) {
            total += candys[i];
        }
        return total;
    }

    private static int eraseOverlapping(int[][] internals) {
        if (internals.length == 0) {
            return 0;
        }
        int size = internals.length;
        Arrays.sort(internals, Comparator.comparingInt(o -> o[1]));
        int total = 0;
        int previous = internals[0][1];
        for (int i = 1; i < size; i++) {
            if (internals[i][0] < previous) {
                total++;
            } else {
                previous = internals[i][1];
            }
        }
        return total;
    }

    private static boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int i = 0;
        while (i < flowerbed.length) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i++] = 1;
                count++;
            }
            if (count >= n) {
                return true;
            }
            i++;
        }
        return false;
    }

    public int findMinArrowShots(int[][] points) {

        int size = points.length;
        if (size == 0) {
            return 0;
        }
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
        int total = 1;
        int start;
        int end;
        int pre = points[0][1];
        for (int[] p : points) {
            start = p[0];
            end = p[1];
            if (start > pre) {
                total++;
                pre = end;
            }
        }
        return total;
    }


    /**
     * 763. 划分字母区间
     * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，
     * 同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：S = "ababcbacadefegdehijhklij"
     * 输出：[9,7,8]
     * 解释：
     * 划分结果为 "ababcbaca", "defegde", "hijhklij"。
     * 每个字母最多出现在一个片段中。
     * 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
     *  
     * <p>
     * 提示：
     * <p>
     * S的长度在[1, 500]之间。
     * S只包含小写字母 'a' 到 'z' 。
     *
     * @param S
     * @return
     */
    public List<Integer> partitionLabels(String S) {

        int[] last = new int[26];
        for (int i = 0; i < S.length(); i++) {
            last[S.charAt(i) - 'a'] = i;
        }
        List<Integer> result = new ArrayList<>();
        int j = 0;
        int arch = 0;
        for (int i = 0; i < S.length(); i++) {
            j = Math.max(j, last[S.charAt(i) - 'a']);
            if (i == j) {
                result.add(i - arch + 1);
                arch = i + 1;
            }
        }
        return result;
    }

    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += (prices[i] - prices[i - 1]);
            }
        }
        return profit;
    }

    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        LinkedList<int[]> outputs = new LinkedList<>();
        for (int[] person : people) {
            outputs.add(person[1], person);
        }
        return outputs.toArray(new int[people.length][2]);
    }

    public boolean checkPossibility(int[] nums) {
        int fix = 0;
        for (int i = 1; i < nums.length && fix <= 1; i++) {
            if (nums[i] >= nums[i - 1]) {
                continue;
            }
            fix++;
            if (i - 2 >= 0 && nums[i] < nums[i - 2]) {
                nums[i] = nums[i - 1];
            } else {
                nums[i - 1] = nums[i];
            }
        }
        return fix <= 1;
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int position = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[position--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        while (n >= 0) {
            nums1[position--] = nums2[n--];
        }
    }

}
